package offer.offer04;

import java.util.Arrays;

/**
 *
 */
public class S60n个骰子的点数 {
    /**
     * 100, 关于n的递推公式还是比较好算的, 这个公式用int[]来存储, 感觉会有好几个int[], 占用空间怎么优化是个问题
     * 注意像如果有2个骰子是掷不出来1的, 这么个情况
     */
    public double[] dicesProbability(int n) {
        double[] res = new double[6];
        Arrays.fill(res, (double)1/6);
        double[] temp1;
        for(int i = 2; i <= n; i++){
            temp1 = new double[5*i + 1];
            for(int j = 0; j < 5*i + 1; j++){
                temp1[j] = arraySum(res, j - 5, j)/6;
            }
            res = temp1;
        }

        return res;

    }
    private double arraySum(double[] input, int start, int end){
        start = Math.max(start, 0);
        end = Math.min(input.length - 1, end);
        double res = 0;
        for(int i = start; i <= end; i++)
            res += input[i];
        return res;
    }
}
